package com.github.sort;

public class QuickSort {
    public static void quickSort(Comparable[] R){
        quickSort(R,0,R.length-1);
    }
    private static void quickSort(Comparable[] R,int low, int high){
        if (high<=low)return;
        int j=partition(R,low,high);
        quickSort(R,low,j-1);
        quickSort(R,j+1,high);

    }
    private static  int partition(Comparable[] R,int low,int high){
        int i=low,j=high+1;
            Comparable v=R[low];
            while (true){
                while (less(R[++i],v ))if (i==high)break;
                while (less(v,R[--j]))if (j==low)break;
                if (i>=j)break;
                exch(R,i,j);
            }
            exch(R,low,j);
            return j;
    }
    private static void exch(Comparable[] R,int i,int j){
      Comparable temp=R[i];
       R[i]=R[j];
       R[j]=temp;
    }
    private static boolean less(Comparable v,Comparable w){
        return v.compareTo(w)<0;
    }
}
